home *** CD-ROM | disk | FTP | other *** search
- Path: anvil.ugrad.cs.ubc.ca!not-for-mail
- From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
- Newsgroups: comp.lang.c
- Subject: Re: C library on computation of matrix determinants
- Date: 6 Mar 1996 15:03:14 -0800
- Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
- Message-ID: <4hl5jiINNbom@anvil.ugrad.cs.ubc.ca>
- References: <wiedem01.4.000E6903@fsuni.rz.uni-passau.de>
- NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
-
- In article <wiedem01.4.000E6903@fsuni.rz.uni-passau.de>,
- WIEDEMANN CHRISTINE <wiedem01@fsuni.rz.uni-passau.de> wrote:
- >I'm looking for a library containing source codes on how to compute a
- >determinant of a matrix. Does anybody know where to find such a library,
- >source codes or algorithms on determinant computation.
-
- One way to do this is to do Gaussian elimination on the matrix, while applying
- the same row operations to an identity matrix. Once you isolate the pivots, the
- determinant is just a product of the diagonal elements. As a bonus, if you
- carry through the operations, you get the matrix inverse.
-
- The naive method of computing the determinant by recursive expansion of
- cofactors/minors yields exponential complexity, whereas Gaussian runs in cubic
- time in the rank of the matrix.
-
- Thus the algorithm you are really looking for is one which reduces the matrix
- to triangular form, from which the determinant readily follows.
-
- I wrote a C module a few years ago that does these kinds of things, but it is
- in archival storage, unfortunately!
-
- Never mind, however---just find a good textbook on the subject of numerical
- analysis. The subject of reducing matrices is usually covered in detail. There
- are variations of the method, because there is some lattitude in choosing
- pivots in attempts to minimize errors. Gaussian elimination is sensitive to
- diagonal elements that are close to zero, since the presence of a true zero
- signals a matrix that is singular (determinant is zero), but it's difficult to
- distinguish between a actual non-zero value, and a perturbed zero value.
-
- There is probably a better newsgroup to ask this question; perhaps something
- related to numerical analysis.
- --
-
-